package partialRDT;

import java.util.HashMap;
import java.util.Map;

import util.MyMath;
import weka.core.Capabilities;
import weka.core.Instance;
import weka.core.Instances;

/**
 * Skew RDT for classification
 * @author tigerzhong
 *
 */
public class SkewRDTClassification extends RDT implements java.io.Serializable,
	java.lang.Cloneable {
    /**
     * serialVersionUID  
     */
    private static final long serialVersionUID = 1L;
    /**
     * Random trees
     */
    private Tree forest[];

    /**
     * Tree node
     * 
     * @author Erheng Zhong
     * 
     */
    private class Node implements java.io.Serializable {
	private static final long serialVersionUID = 1L;
	public boolean leafFlag = false;	//Leaf flag
	public double splitValue;		//Point value in the feature used for splitting
	public int splitIdx;			//The index of the feature used for splitting
	public int dataDistribution[];		//Classes information at one node
	public int left;			//Index of left node
	public int right;			//Index of right node
    }

    /**
     * Trees, node set
     * 
     * @author Erheng Zhong
     * 
     */
    private class Tree implements java.io.Serializable {
	private static final long serialVersionUID = 1L;
	public Map<Integer, Node> nodes = new HashMap<Integer, Node>();	//Hash Table to storage the tree node
    }
    
    @Override
    public void buildClassifier(Instances data) throws Exception {
	init();
	srcData = new Instances(data);
	generateTrees();
	srcData.delete();
	srcData = null;
    }

    /**
     * Classify Instance
     */
    @Override
    public double classifyInstance(Instance item) throws Exception {
	double v[] = distributionForInstance(item);
	return MyMath.getMaxIdx(v);
    }

    /**
     * Get the Distribution of Instance
     */
    @Override
    public double[] distributionForInstance(Instance item) throws Exception {
	double v[] = new double[item.numClasses()];
	double sum = 0.0;
	for (int i = 0; i < getNumTrees(); i++) {
	    int pre[] = classifyData(0, item, i);
	    double cnt = 0.0;
	    for (int j = 0; j < pre.length; j++)
		cnt += pre[j];
	    for (int j = 0; j < pre.length; j++) {
		v[j] += pre[j] / cnt;
		sum = sum + pre[j] / cnt;
	    }
	}
	//Normalize
	for (int i = 0; i < item.numClasses(); i++) {
	    v[i] /= sum;
	}
	return v;
    }

    /**
     * Initialize the random trees
     */
    private void init() {
	forest = new Tree[getNumTrees()];
	for (int i = 0; i < getNumTrees(); i++) {
	    forest[i] = new Tree();
	}
    }

    /**
     * Generate Trees
     */
    private void generateTrees() {
	for (int i = 0; i < getNumTrees(); i++) {
	    buildTree(0, 0, srcData, i,
		    new boolean[srcData.numAttributes() - 1]);
	}
    }

    /**
     * Build single tree
     * 
     * @param depth
     * @param nodeID
     * @param data
     * @param treeID
     */
    private void buildTree(int dp, int nid, Instances data, int tid,
	    boolean[] used) {
	/* Initialize */
	Node current = new Node();
	current.dataDistribution = new int[data.numClasses()];
	for (int i = 0; i < data.numInstances(); i++) {
	    current.dataDistribution[(int) data.instance(i).classValue()]++;
	}
	/* Stop splite? */
	boolean allUse = true;
	for (int i = 0; i < used.length; i++) {
	    if (!used[i]) {
		allUse = false;
		break;
	    }
	}
	boolean allSame = false;
	int largest = -1;
	int catNum[] = new int[data.numClasses()];
	for (int i = 0; i < data.numInstances(); i++) {
	    catNum[(int) (data.instance(i).classValue())]++;
	    if (catNum[(int) (data.instance(i).classValue())] > largest)
		largest = catNum[(int) (data.instance(i).classValue())];
	}
	if (largest >= (int)(data.numInstances()*getRatio()))
	    allSame = true;
	if (allSame || allUse || dp >= getDepth()
		|| data.numInstances() <= getMinNum()) {	//Pure
	    current.leafFlag = true;
	    current.splitValue = 0.0;
	    current.splitIdx = -1;
	    current.left = -1;
	    current.right = -1;
	} else {	//Split
	    int splitIdx = MyMath.generateRand(0, data.numAttributes() - 1);
	    while (used[splitIdx])
		splitIdx = MyMath.generateRand(0, data.numAttributes() - 1);
	    if (data.attribute(splitIdx).isNominal()
		    && data.numDistinctValues(splitIdx) <= 2)
		used[splitIdx] = true;
	    double splitValue = data.meanOrMode(splitIdx);
	    /*
	     * double miV = Double.MAX_VALUE; double maV = -Double.MAX_VALUE;
	     * for(int i=0;i<data.numInstances();i++){ miV = Math.min(miV,
	     * data.instance(i).value(splitIdx)); maV = Math.max(maV,
	     * data.instance(i).value(splitIdx)); } splitValue =
	     * MyMath.generateRand(miV, maV);
	     */
	    current.leafFlag = false;
	    current.splitIdx = splitIdx;
	    current.splitValue = splitValue;
	    Instances left = new Instances(data, 0);
	    Instances right = new Instances(data, 0);
	    for (int i = 0; i < data.numInstances(); i++) {
		if (data.instance(i).value(splitIdx) < splitValue)	//Left
		    left.add((Instance) data.instance(i).copy());
		else
		    right.add((Instance) data.instance(i).copy());	//Right
	    }
	    //Keep on splitting?
	    if (left.numInstances() >= getMinNum()) {
		current.left = nid * 2 + 1;
		buildTree(dp + 1, nid * 2 + 1, left, tid, used);
	    } else
		current.left = -1;
	    if (right.numInstances() >= getMinNum()) {
		current.right = nid * 2 + 2;
		buildTree(dp + 1, nid * 2 + 2, right, tid, used);
	    } else
		current.right = -1;
	}
	forest[tid].nodes.put(nid, current);	//Update
	return;
    }

    /**
     * Classify data
     * 
     * @param nid
     * @param item
     * @param tid
     * @return classValue
     */
    private int[] classifyData(int nid, Instance item, int tid) {
	if (forest[tid].nodes.get(nid).leafFlag)
	    return forest[tid].nodes.get(nid).dataDistribution;
	else {
	    int si = forest[tid].nodes.get(nid).splitIdx;
	    double sv = forest[tid].nodes.get(nid).splitValue;
	    if (item.value(si) < sv) {	//Left
		if (forest[tid].nodes.get(nid).left != -1)
		    return classifyData(forest[tid].nodes.get(nid).left, item,
			    tid);
		else
		    return forest[tid].nodes.get(nid).dataDistribution;
	    } else {	//Right
		if (forest[tid].nodes.get(nid).right != -1)
		    return classifyData(forest[tid].nodes.get(nid).right, item,
			    tid);
		else
		    return forest[tid].nodes.get(nid).dataDistribution;
	    }
	}
    }

    @Override
    public Capabilities getCapabilities() {
	return null;
    }
}
